An Online Optimization Approach for Multi-Agent Tracking of Dynamic Parameters in the Presence of Adversarial Noise

摘要

This paper addresses tracking of a moving target in a multi-agent network.The target follows a linear dynamics corrupted by an adversarial noise, i.e.,the noise is not generated from a statistical distribution. The location of thetarget at each time induces a global time-varying loss function, and the globalloss is a sum of local losses, each of which is associated to one agent. Agentsnoisy observations could be nonlinear. We formulate this problem as adistributed online optimization where agents communicate with each other totrack the minimizer of the global loss. We then propose a decentralized versionof the Mirror Descent algorithm and provide the non-asymptotic analysis of theproblem. Using the notion of dynamic regret, we measure the performance of ouralgorithm versus its offline counterpart in the centralized setting. We provethat the bound on dynamic regret scales inversely in the network spectral gap,and it represents the adversarial noise causing deviation with respect to thelinear dynamics. Our result subsumes a number of results in the distributedoptimization literature. Finally, in a numerical experiment, we verify that ouralgorithm can be simply implemented for multi-agent tracking with nonlinearobservations.